package com.bing.java.search;

/**
 * 查找最大乘积
 * @author bing
 *
 * 2019年11月18日 下午2:22:48
 * 
 * 给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)。
 */
public class SearchMaxChenji {

	public static void main(String[] args) {
		int [] num = {20,5,6,-25,-10,0,2,3,-2};
		int len = num.length;
		
		long maxData = MaxDataMethod(num,len);
		System.out.println(maxData);
	}

	private static long MaxDataMethod(int[] num, int len) {
		int max1 = 0;
		int max2 = 0;
		int max3 = 0;
		int min1 = 0;
		int min2 = 0;
		for (int i = 0; i < num.length; i++) {
			if(num[i] != 0){
				if(num[i] > max1){
					max3 = max2;
					max2 = max1;
					max1 = num[i];
				} else if (num[i] > max2) {
					max3 = max2;
					max2 = num[i];
				} else if (num[i] > max3){
					max3 = num[i];
				} else if (num[i] < min1) {
					min2 = min1;
					min1 = num[i];
				} else if (num[i] >min1 && num[i] < min2){
					min2 = num[i];
				}
			} else {
				continue;
			}
		}
		System.out.println(max1+"\t" + max2+"\t"+ max3+"\t"+min1+"\t"+min2);
		long max = Math.max(max1*max2*max3, max1*min1*min2);
		return max;
	}
}
